package com.dubious.interview.euler;

import java.util.HashSet;
import java.util.Set;

public class Problem21 {

    public static int run(int base)
    {
        // strategy:
        // Build a map of <int> -> <sum of divisors> and use this map to find amicable numbers.  Then sum.
        
        long[] sumsOfDivisors = new long[base + 1];
        // track the max sum so we have an idea of the efficacy of the algorithm
        for(int i = 1; i <= base; i++)
        {
            sumsOfDivisors[i] = getSumOfDivisors(i);
        }
        
        Set<Long> amicableNumbers = new HashSet<Long>();
        for(int i = 1; i <= base; i++)
        {
            // NOTE: It is possible that this will not work if there is a match where one of the pair
            //       is above base value.
//            if(sumsOfDivisors[i] > base)
//            {
//                throw new RuntimeException("A sum of divisors is greater than the input.  Not sure the algorithm will work");
//            }
            
            if(sumsOfDivisors[i] > Integer.MAX_VALUE)
            {
                throw new RuntimeException("A sum of divisors is greater than int max value.  Int-based array lookup will fail");
            }
            
            if(sumsOfDivisors[i] <= base && i != sumsOfDivisors[i] && i == sumsOfDivisors[(int)sumsOfDivisors[i]])
            {
                // found an amicable pair
                amicableNumbers.add(Long.valueOf(i));
                amicableNumbers.add(Long.valueOf(sumsOfDivisors[i]));
            }
        }
        
        int amicableNumberSum = 0;
        for(Long amicableNumber : amicableNumbers)
        {
            amicableNumberSum += amicableNumber;
        }
        
        return amicableNumberSum;
    }
    
    private static long getSumOfDivisors(long number)
    {
        Set<Long> divisors = Utilities.getDivisors(number);
        divisors.remove(Long.valueOf(number));
        
        long sumOfDivisors = 0;
        for(Long divisor : divisors)
        {
            sumOfDivisors += divisor;
        }
        
        return sumOfDivisors;
    }
}
